class Solution:
    def shortestPalindrome(self, s: str) -> str:
        # 处理空字符串
        if not s:
            return ""
        # 对字符串进行预处理，添加特殊字符以统一处理奇偶长度的回文串
        t = '^'  + '#'.join(s)  + '$'
        lent = len(t)
        # 记录当前右边界最大的回文子串的中心和右边界
        box_m = box_r = 0
        # 存储以每个位置为中心的最长回文子串的半径
        h_len = [0] * lent
        # 记录从字符串起始位置开始的最长回文子串的中心和半径
        start = 0
        r = 0
        for i in range(1, lent - 1):
            # 初始化当前回文半径,从半径0开始
            cur_l = 0
            if i < box_r:
                # 利用之前的回文信息进行初始化
                cur_l = min(h_len[2 * box_m - i], box_r - i)

            # 尝试扩展回文串
            while t[i - cur_l-1] == t[i + cur_l+1]:
                cur_l += 1
                box_m = i
                box_r = i + cur_l
            # 更新当前回文子串的信息
            h_len[i] = cur_l

            # 检查是否是以字符串起始位置开始的回文串
            if i - cur_l == 1:
                if cur_l > r:
                    start = i
                    r = cur_l
        # print(start,r)
        # 计算从字符串起始位置开始的最长回文子串在原字符串中的结束位置
        end = (start + r) // 2
        # 获取需要添加到原字符串前面的部分
        c = s[end + 1:][::-1]
        # print(t)
        # print(h_len)
        return c + s